package com.beautiful.xin.rbtree;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;
import java.util.TreeMap;

/**
 * @author xuqingxin 2021/7/7 11:32 上午
 */
public class TreeNode {
    private int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        left = right = null;
    }


    public static void mirrorTreeWithQueue(TreeNode root) {
        if (root == null) {
            return;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();

            TreeNode temp = poll.left;
            poll.left = poll.right;
            poll.right = temp;

            if (poll.right != null) {
                queue.add(poll.right);
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
        }
    }


    /**
     * 镜像二叉树 递归版
     *
     * @param root
     */
    public static void mirrorTree(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;

        mirrorTree(root.left);
        mirrorTree(root.right);
    }


    /**
     * 层次遍历 --------------------------------
     */
    public static ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        LinkedList<TreeNode> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            result.add(poll.val);
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return result;
    }


    /**
     * 非递归版 --------------------------------
     */
    public static void preOrderUnRecur(TreeNode head) {
        if (head == null) {
            return;
        }

        Stack<TreeNode> s = new Stack<>();
        s.add(head);

        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            System.out.println(node.val + "");

            if (node.right != null) {
                s.add(node.right);
            }
            if (node.left != null) {
                s.add(node.left);
            }
        }
    }

    public static void inOrderUnRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> s = new Stack<>();
        while (!s.isEmpty() || head != null) {
            if (head != null) {
                s.add(head);
                head = head.left;
            } else {
                head = s.pop();
                System.out.println(head.val + "");
                head = head.right;
            }
        }
    }


    public static void postOrderUnRecur(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        s1.add(head);
        while (!s1.isEmpty()) {
            head = s1.pop();
            s2.add(head);

            if (head.left != null) {
                s1.add(head.left);
            }
            if (head.right != null) {
                s1.add(head.right);
            }
        }

        while (!s2.isEmpty()) {
            System.out.println(s2.pop().val + "");
        }

    }

    /**
     * 递归版本  --------------------------------
     */
    public static void preOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val + "");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    public static void inOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left);
        System.out.println(root.val + "");
        inOrderRecur(root.right);
    }

    public static void postOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrderRecur(root.left);
        postOrderRecur(root.right);
        System.out.println(root.val + "");
    }


}
